#include <cstdlib> 
#include <cctype> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <sstream> 
#include <map> 
#include <set> 
#include <queue> 
#include <stack> 
#include <fstream> 
#include <iomanip> 
#include <bitset> 
#include <list> 
//#include <strstream> 
using namespace std; 
#define REP(i,n) for(i=0;i<(n);++i) 
#define FOR(i,l,h) for(i=(l);i<=(h);++i) 
#define FORD(i,h,l) for(i=(h);i>=(l);--i) 
typedef vector<int> VI; 
typedef vector<double> VD; 
//typedef long long LL; 

class DivideAndShift 
{ 
        public: 
    struct node 
    {
      int  n, m;
    }N, P;
    int prim[20];
    int len , res;
    void divide(int N)
    {
      len = 0;
      for(int i = 2; i * i <= N; i ++)
      {
        if(N % i == 0)
        {
          prim[len] = i;
          len ++;
          while(N % i == 0)
          {
            N /= i;
          }
        }
      }
      if(N != 1)
      {
        prim[len ++] = N;
      }
    }
    void dfs(int n, int m, int depth)
    {
      int curres = depth + m;
      if(curres > depth + n - m)
        curres = depth + n - m;
      if(curres < res)
        res = curres;
      //return;
      for(int i = 0; i < len; i ++)
      {
        if(n % prim[i] == 0)
        {
          dfs(n/prim[i], m % (n/prim[i]), depth + 1);
        }
      }
    }
        int getLeast(int N, int M) 
        { 
      M = M - 1;
      divide(N);
      res = 0x7ffffff;
      dfs(N, M, 0);
      return res;
        } 
        
 
}; 


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor